/*
 * @Author: 生俊甫 1758142861@qq.com
 * @Date: 2024-10-22 16:59:19
 * @LastEditors: 生俊甫 1758142861@qq.com
 * @LastEditTime: 2024-10-24 13:55:09
 * @FilePath: /sjf/2024-project/2024_centos/test_to_c/408_str/2021.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <iostream>


#define MAXv 6
typedef struct MGraph
{
    int numVertices,numEdges;//定义图的顶点个数和边数
    char VerticesList[MAXv];//顶点数据
    int Edge[MAXv][MAXv];//定义邻接矩阵
}MGraph;

/**
 * 41.
 * 该题目表示的是寻找一个无向图中所有度为奇数的顶点有degree个
 * 然后如果degree为不大于2的偶数(0或2)
 * 那么就称该图中包含EL路径
 * 
 * 1、整体思路：
 * 因为该图是一个无向图并且使用了邻接矩阵存储
 * 因此我们只需要依次遍历每一行中每个元素的值，统计有多少个不为0的值
 * 在每一行统计结束之后判断该行不为0的值是否为奇数，如果是奇数就count++
 * 最后遍历玩每一行之后，判断count是否是0或2，是就返回1，不是就返回0
 * 
 * 3.时间复杂度O(n^2)，空间复杂度O(1)-->没有额外的使用空间
 */

int IsExitEL(MGraph G)
{
    int count = 0;
    for(int i = 0; i<G.numVertices; i++)
    {
        int degree = 0;
        for(int j = 0; j < G.numVertices; j++)
        {
            if(G.Edge[i][j] != 0)   
                degree++;
        }
        if(degree % 2 != 0)
            count++;
    }
    if(count == 0 || count == 2)
        return 1;
    return 0;
}

/**
 * 42.
 * 
 */

void cmpCountSort(int a[],int b[],int n)
{
    int* count = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++)
        count[i] = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] < a[j])
                count[j]++;
            else
                count[i]++;
        }
    }
    for(int i = 0; i < n; i++)
        b[count[i]] = a[i];
    free(count);
}

int main()
{
    return 0;
}